Diagonal Operators appear in a wide variety of different quantum computational algorithms, and their efficient implementation is essential for creating practical implementations on proposed quantum computational architectures. In the case of exact diagonal operator decompositions, where the precision of approximation is exact, the exact decompositions exhibit the property that all entanglement occurs through the use of elementary CNOT gates which have relatively small fault-tolerant cost. This results in the entirety of the quantum resource complexity being placed in the number of single-qubit rotations, which, in these methods, has in general an exponential scaling. In some cases, exact decompositions of diagonal operators produce single qubit rotations that are difficult or impossible to implement exactly using the Clifford+T universal gate set. Hence single-qubit approximation methods are required in general.
Since exact decomposition methods are based around the construct of performing a tensor product type decomposition using a complete functional basis representation of the operator space, there is little to no freedom in how phase angles are distributed in the corresponding circuit. This is largely a consequence of the decompositions being exact, but it has the undesirable side effect of having only a single way of implementing the associated quantum circuit under the exact decomposition.
If the phases appearing in the diagonal unitary are chosen from a finite collection of phases, the exact methods in general produce an overly pessimistic (large) number of single-qubit rotations in an attempt to delocalize the rotations required over the entire n-qubit operational space. In some cases, highly non-local correlations in phase values can lead to small numbers of single-qubit rotations. Since these methods use only elementary CNOT entanglement operators, there is essentially zero fault-tolerant implementation cost associated with the entanglement properties of the resulting circuit due to the low cost of implementing Clifford gates in, for example, typical quantum error correction codes. However, if the number of distinct phases is small and/or the distribution of phases along the diagonal is highly localized to a particular region of the operator space, such non-local decompositions lead to exponential scaling in the number of single qubit rotations. Since in general the rotation angles produced by these methods are not exactly implementable over the HT basis, approximation methods are required for their decomposition into this basis. However, since these methods result in zero fault-tolerant implementation cost in the entangling operations, the fault-tolerant cost of the circuit can rapidly grow to the point of being infeasible on practical implementations of quantum computing architectures. Accordingly, approximate methods are needed.